Search for: All records

We consider the classical single-source shortest path problem in directed weighted graphs. D. Eppstein proved recently an Ω(n³) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this Ω(n³) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm. 

Abstract This study analyzes up‐to‐date gravity data in the Galapagos triple junction region to understand crustal structure and melt distribution beneath the propagating Cocos‐Nazca spreading center (CNSC). Application of a standard thermal model to the mantle Bouguer gravity anomaly (MBA) does not appear to result in a realistic crustal thickness in this region. The cross‐CNSC MBA profiles flatten and axial values increase from east toward the western end of the CNSC. A simple smoothing filter applied to the standard thermal model with different filter widths can explain the progressive flattening of the MBA and is interpreted as different distribution widths (concentrations) of partial melt in the mantle. The east‐west residual MBA gradient along the CNSC is similar to the east flank of the East Pacific Rise (EPR), suggesting that the along‐CNSC gradient could partly reflect the shallow mantle properties associated with the EPR.